package linklist;

import linklist.LeetCode_2;
import org.junit.Test;


/**
 * @author kunkun
 * @className LeetCode_148
 * @Description ...
 * @date 2025/3/23 19:42
 */
public class LeetCode_148 {

    public class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }



    @Test
    public void test(){
        ListNode head = new ListNode(4, new ListNode(2, new ListNode(1, new ListNode(3, null))));
        ListNode list = sortList(head);
        printList(list);
    }

    private void printList(ListNode list) {
        ListNode temp = list;
        while (temp!=null){
            System.out.print(temp.val+" ");
            temp=temp.next;
        }
    }

    public ListNode sortList(ListNode head) {
        //1. 特殊条件返回
        if (head ==null || head.next == null){
            return head;
        }
        //2. 寻找中点，进行归并
        ListNode fast = head.next,slow = head;
        while (fast!=null && fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode head2 = slow.next;
        slow.next = null;
        //3. 对左右进行递归
        ListNode left = sortList(head);
        ListNode right = sortList(head2);

        //4. 合并操作
        ListNode result = new ListNode(0,null);
        ListNode temp = result;
        do {
            if (left.val<right.val){
                temp.next = left;
                temp=temp.next;
                left=left.next;
            }else {
                temp.next = right;
                temp = temp.next;
                right = right.next;
            }
        }while (left!=null && right!=null);

        //3. 判断
        if (left==null){
            temp.next = right;
        }else {
            temp.next = left;
        }
        return result.next;

    }




}
